

#include <stdio.h>
#include <stdlib.h>

#include "binary_tree.h"



static BSTREE_NODE *create_node(int data)
{
    BSTREE_NODE *node = malloc(sizeof(BSTREE_NODE));

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

static void destroy_node(BSTREE_NODE *node)
{
    free(node);
}
static void clear(BSTREE_NODE **root)
{
    if(*root)
    {
        /*清空左子树*/
        clear(&(*root)->left);
        /*清空右子树*/
        clear(&(*root)->right);

        /*销毁节点*/
        destroy_node(*root);

        *root = NULL;
    }
}

static void insert(BSTREE_NODE *node, BSTREE_NODE **root)
{
    /*如果为空树*/
    if(!*root)
    {
        *root = node;
    }
    /*node节点存在*/
    else if(node)
    {
        /*如果要插入节点的值比当前节点值小*/
        if(node->data < (*root)->data)
        {
            insert(node, &(*root)->left);
        }
        else
        {
            insert(node, &(*root)->right);
        }
    }
}

/*返回以参数root的目标所指向的节点为根的子树地址，*/
static BSTREE_NODE **find(int data, BSTREE_NODE **root)
{
    if(!*root)
    {
        return root;
    }

    if(data < (*root)->data)
    {
        return find(data, &(*root)->left);
    }
    else if(data > (*root)->data)
    {
        return find(data, &(*root)->right);
    }
    else
    {
        return root;
    }
}

static void pretravel(BSTREE_NODE *root)
{
    if(root)
    {
        printf("%d ", root->data);
        pretravel(root->left);
        pretravel(root->right);
    }
}
static void  intravel(BSTREE_NODE *root)
{
    if(root)
    {
        intravel(root->left);
        printf("%d ", root->data);
        intravel(root->right);
    }
}
static void  postravel(BSTREE_NODE *root)
{
    if(root)
    {
        postravel(root->left);
        postravel(root->right);
        printf("%d ", root->data);
    }
}

static int height(BSTREE_NODE *root)
{
    if(root)
    {
        int lh = height(root->left);
        int rh = height(root->right);

        return (lh > rh ? lh: rh) + 1;
    }

    return 0;
}


static void print(BSTREE_NODE *root, int level)
{
    int i;
    if(root)
    {
        
        print(root->right, level+1);
        for(i=0; i<level; i++)
        {
            printf("   ");
        }
        printf("%d\n", root->data);
        print(root->left, level+1);

    }
}    



/*建树*/
BSTREE *bstree_create(void)
{
    BSTREE *bstree = malloc(sizeof(BSTREE));
    bstree->root = NULL;
    bstree->size = 0;

    return bstree;
}

/*销毁树*/
void bstree_destroy(BSTREE *bstree)
{
    bstree_clear(bstree);
    free(bstree);
}

/*插入节点*/
void bstree_insert(BSTREE *bstree, int data)
{
    insert(create_node(data), &bstree->root);

    ++bstree->size;
}



/*删除节点*/
int bstree_erase(BSTREE *bstree, int data)
{
    /*要找到存放该节点地址的变量的地址，即该节点父节点的left或者right的地址
     *因为其父节点的left或者right会被赋值为当前节点右节点的地址
     *参数二必须为二级指针，因为返回的存放当前节点地址变量的地址，所以传递进去的也应该是节点地址变量的地址
     * */
    BSTREE_NODE **node = find(data, &bstree->root);

    if(*node)
    {
        /*将匹配节点的左子树插入其右子树*/
        insert((*node)->left, &(*node)->right);
        
        BSTREE_NODE *temp = *node;
        /*用匹配节点的右子树的根节点取代匹配节点*/
        *node = (*node)->right;

        /*删除匹配节点*/
        destroy_node(temp);

        --bstree->size;

        return 1;

    }

    return 0;
}

/*删除所有匹配数据*/
void bstree_remove(BSTREE *bstree, int data)
{
    while(bstree_erase(bstree,data));
}

/*清空*/
void bstree_clear(BSTREE *bstree)
{
    /*销毁所有子树*/
    clear(&bstree->root);
    bstree->size = 0;
}

/*更新节点*/
void bstree_update(BSTREE *bstree, int old, int new)
{
    while(bstree_erase(bstree,old))
    {
        bstree_insert(bstree,new);
    }
}


/*判断值为data的节点是否存在*/
int bstree_exist(BSTREE *bstree, int data)
{
    if (*find(data, &bstree->root) != NULL)
    {
        return 1;
    }
    
    return 0;
}

/*先序遍历*/
void bstree_pretravel(BSTREE *bstree)
{
    pretravel(bstree->root);
    printf("\n");
}

/*中序遍历*/
void bstree_intravel(BSTREE *bstree)
{
    intravel(bstree->root);
    printf("\n");
}

/*后序遍历*/
void bstree_postravel(BSTREE *bstree)
{
    postravel(bstree->root);
    printf("\n");
}

/*节点个树*/
int bstree_size(BSTREE *bstree)
{
    return bstree->size;
}

/*高度*/
int bstree_height(BSTREE *bstree)
{
    return height(bstree->root);
}


/*打印*/
void bstree_print(BSTREE *bstree)
{
    print(bstree->root, 0);
}


